package my.jwds.p34;

public class SearchRange {

    public static void main(String[] args) {

        Solution obj = new Solution();
        long start = System.currentTimeMillis();
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    static class Solution {

        public int[] searchRange(int[] nums, int target) {
            int index = searchIndex(nums,0,nums.length-1,target);
            if (index == -1)return new int[]{-1,-1};
            int left = index;
            while(true){
                int temp = searchIndex(nums,0,left-1,target);
                if (temp == -1)break;
                left = temp;
            }
            int right = index;
            while(true){
                int temp = searchIndex(nums,right+1,nums.length-1,target);
                if (temp == -1)break;
                right = temp;
            }
            return new int[]{left,right};
        }

        int searchIndex(int [] nums,int lower,int upper,int target){
            while(lower <= upper){
                int mid = (lower+upper)/2;
                if (nums[mid] > target){
                    upper = mid-1;
                }else if (nums[mid] < target){
                    lower = mid+1;
                }else{
                    return mid;
                }
            }
            return -1;
        }

    }

    static class Solution1 {

        public int[] searchRange(int[] nums, int target) {
            int left = searchIndex(nums,target,true);
            int right = searchIndex(nums,target,false);
            return new int[]{left,right};
        }

        int searchIndex(int [] nums,int target,boolean flag){
            int lower = 0,upper = nums.length-1,res = -1;
            while(lower <= upper){
                int mid = (lower+upper)/2;
                if (nums[mid] > target){
                    upper = mid-1;
                }else if (nums[mid] < target){
                    lower = mid+1;
                }else {
                    if (flag){
                        upper = mid -1;
                    }else{
                        lower = mid +1;
                    }
                    res = mid;
                }
            }
            return res;
        }

    }
}